package com.xiyou.week04.binaryReactor;

/**
 * 面试题 04.06. 后继者
 *
 * @ClassName：InorderSuccessor
 * @Author：西柚
 * @Date：2022/1/22 11:03 下午
 * @Versiion：1.0
 */
public class InorderSuccessor {

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        return getNext(root, p.val);
    }

    public TreeNode getNext(TreeNode root, int val) {
        TreeNode ans = null;
        TreeNode curr = root;
        while (curr != null) {
            if (curr.val == val) {
                if (curr.right != null) {
                    ans = curr.right;
                    while (ans.left != null) {
                        ans = ans.left;
                    }
                }
                break;
            }
            if (val < curr.val ) {
                if (ans == null || ans.val > curr.val) {
                    ans = curr;
                }
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        return ans;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
